package com.company.algo.DP.subseqProblem.DiscontinuousSubsequences;

import com.company.algo.debugUtils.DebugUtils;

import java.util.*;

/**
 * 1713. 得到子序列的最少操作次数
 */
public class minimum_operations_to_make_a_subsequence {
    /**
     *  target.len - 最长公共子序列 = ans
     *     dp[m][n]为下标m之前的target数组和下标n之前的arr数组的最长公共子序列长度
     *     dp[m][n] = dp[m-1][n-1] + 1, if target[m]==arr[n]
     *              = max(dp[m][n-1], dp[m-1][n]) if target[m] == arr[n]
     *     dp[0][0] = 0
     *     -----超时(O(mn))，需要改进解法---
     * @param target
     * @param arr
     * @return
     */
    public int minOperations1(int[] target, int[] arr) {
        int m = target.length;
        int n = arr.length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i<=m; i++){
            for(int j=1;j<=n;j++){
                if(target[i-1]==arr[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        DebugUtils.printMatrix(dp);
        int maxLen = dp[m][n];
        return m - maxLen;
    }

    /**
     * 将arr中与target相交的元素标记其下标并得到一个新的数组，如
     *     target=[3,0,2], arr = [1,3,2] -> arr' = [0,2]（去掉不在 target 中的元素 1）
     *     同样的操作得到target的下标数组 target' = [1,2,3]
     *     则求原数组的最长公共子序列等价于求上述转换后的两数组的最长公共子序列。
     *     又由于target'是严格单调递增的，因此arr'在最长公共子序列中的部分也必须是单调递增的，
     *      因此问题进一步转换为求arr'的最长递增子序列长度
     *      -----超时，需要改进解法---
     * @param target
     * @param arr
     * @return
     */
    public int minOperations2(int[] target, int[] arr) {
        int n = target.length;
        int m = arr.length;
        Map<Integer,Integer> pos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            pos.put(target[i],i);
        }
        List<Integer> arr_ = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if (pos.containsKey(arr[i])) arr_.add(pos.get(arr[i]));
        }
        if (arr_.size() < 1) return n;
        //最长递增子序列
        int[] dp = new int[arr_.size()];
        Arrays.fill(dp,1);
        int res = 0;
        for (int i = 1; i < arr_.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (arr_.get(i)>arr_.get(j)) dp[i] = Math.max(dp[i],dp[j]+1);
            }
            res = Math.max(res,dp[i]);
        }
        return n - res;
    }

    public int minOperations(int[] target, int[] arr) {
        int n = target.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            map.put(target[i],i);
        }
        List<Integer> newArr = new ArrayList<>();
        for (int x : arr) {
            if (map.containsKey(x)) newArr.add(map.get(x));
        }
        if (newArr.size() < 1) return n;
        int[] nums = new int[newArr.size()];
        //贪心+二分寻找最长递增子序列
        int end = 0;
        nums[0] = newArr.get(0);
        for (int i = 1; i < newArr.size(); i++) {
            int tar = newArr.get(i);
            if (tar>nums[end]) nums[++end] = tar;
            else {
                int left=0, right = end;
                while (left<right){
                    int mid = (left+right)/2;
                    if (nums[mid]<tar)left = mid+1;
                    else right = mid;
                }
                nums[left] = tar;
            }
        }
        return n - end - 1;
    }


    public static void main(String[] args) {
        int[] target = {5,10,8,11,3,15,9,20,18,13};
        int[] arr = {15,8,2,9,11,20,8,11,7,2};
        minimum_operations_to_make_a_subsequence Main = new minimum_operations_to_make_a_subsequence();
        System.out.println(Main.minOperations(target, arr));
    }
}
